Статья 5215

Название статьи

ОЦЕНКА АЛГОРИТМОВ РАСЧЕТА РАССТОЯНИЯ СТРОК ДНК

Авторы

Мельников Борис Феликсович, доктор физико-математических наук, профессор, кафедра прикладной математики и информатики,Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), barmaley62@yandex.ru
Пивнева Светлана Валентиновна, кандидат педагогических наук, доцент, кафедра высшей математики и математического моделирования, Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), tlt.swetlana@rambler.ru
Трифонов Максим Андреевич, аспирант, Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), trifonov_max@mail.ru

Индекс УДК

621.317.7

Аннотация

Актуальность и цели. Часто требуется измерить различие или расстояние между двумя строками (например, в эволюционных, структуральных или функциональных исследованиях биологических строк). Так как строковые последовательности митохондриальных ДНК приблизительно составляют 17 000 символов {a, g, c, t}, то для решения поставленной задачи были выбраны алгоритмы нечеткого сравнения, рассчитывающие расстояние за полиноминальное время. В рамках исследования при расчете метрик различными ранее известными алгоритмами неточного сравнения строк были получены различные результаты. Цель исследования: разработка методов качественной оценки полученных результатов. Разработка качественных оценок позволит сделать выбор более приемлемого алгоритма, что улучшит исследования в различных предметных областях.
Материалы и методы. В качестве метода исследования применятся теория треугольной нормы в метрическом пространстве.
Результаты. Исходные данные были получены из банка данных NCBI и случайным образом выбраны 30 строковых последовательностей митохондриальных ДНК. В результате работы алгоритмов сравнения 30 строковых последовательностей приведены качественные оценки.
Выводы. По полученным качественным оценкам метрик был определен наилучший алгоритм сравнения строковых последовательностей.

Ключевые слова

метрическая оценка, алгоритмы, мультиэвристический подход.

Скачать статью в формате PDF
Список литературы

1. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология / Д. Гасфилд. – СПб. : Невский диалект, БХВ-Петербург, 2003. – 654 с.
2. Бойцов, Л. Использование хеширования по сигнатуре для поиска по сходству /Л. Бойцов // Прикладная математика и информатика. – 2000. – № 7.
3. Мельников, Б. Ф. Параллельная реализация мультиэвристического подхода в задаче сравнения генетических последовательностей / Б. Ф. Мельников, А. Г. Панин // Вектор науки Тольяттинского государственного университета. – 2012. - № 4 (22). – С. 83–86.
4. NCBI: nucleotide database, 2015. – URL: http://www.ncbi.nlm.nih.gov/nuccore.
5. Пивнева, С. В. Моделирование задач дискретной оптимизации / С. В. Пивнева, М. А. Трифонов // Вектор науки Тольяттинского государственного университета. – 2010. – № 3. – С. 28–30.
6. Мельников, Б. Ф. Кластеризация ситуаций и принятие решений в задачах дискретной оптимизации / Б. Ф. Мельников, Е. А. Мельникова // Известия высших учебных заведений. Поволжский регион. Сер. Естественные науки. – 2007. –№ 2. – С. 25–28.
7. Сайфу ллина, Е. Ф. Об алгоритмах восстановления графа по вектору степеней второго порядка / Е. Ф. Сайфуллина, Р. И. Семенов // Эвристические алгоритмы и распределенные вычисления. – 2014. – Т. 1, № 2. – С. 43–57.
8. Needleman, S. A general method applicable to the search for simi-larities in the amino acid sequence of two proteins / S. Needleman, C. Wunsch // Journal of Molecular Bi-ology. – 1970. – № 48 (3). – P. 443–453.
9. Winkler, W. String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage / W. Winkler // Proceedings of the Section on Survey Research Methods. – American Statistical Association, 1990. – P. 354–359.
10. Ewing, B. Base-calling of automated sequencer traces using phred. I. Accuracy assessment/ B. Ewing, L. Hillier, M. Wendl, Р. Green // Genome Res. – 1998. – № 8 (3). –P. 175–185.
11. Altschul, S. F. Amino acid substitution matrices from an information theoretic perspective / S. F. Altschul // Journal of Molecular Biology. – 1991. – № 219 (3). –P. 555–565.

 

Дата создания: 31.07.2015 11:44
Дата обновления: 20.10.2015 14:58